// Trie de conteudo generico.
// Mapeia uma string a uma lista do tipo T (template)

#ifndef GTrie_hpp
#define GTrie_hpp

#include <vector>
#include <string>

template <typename T> class GTrie {

	// Vetor de valores do no
	std::vector<T> 		 values;

	// Filhos do no
	std::vector<GTrie *> children;

	// Quantidade de filhos do no
	int					 qtyChildren;

	// Pai do no. 0 se raiz
	GTrie<T> *			 dad;

	// Caracter pelo qual o no se conecta ao seu pai
	char				 dadConnection;
public:
	// Construtor do no
	GTrie(GTrie<T> * dad = 0, char dadConnection = -1);

	// Destrutor do no
	virtual ~GTrie();

	// Insere um elemento na trie (chaves iguais resultam em acrescimo na lista de valores)
	void insert(std::string path, T value);

	// Resgata todos os valores de um no acessado pela chave dada.
	// Se tal no nao existir, retorna vetor vazio.
	std::vector<T> retrieve(std::string path);

	// Resgata todos os valores de um no acessado pela chave dada.
	// Se tal no nao existir, retorna vetor vazio.
	// Ponteiro rpointer e' alterado para apontar para o no' que possui
	// tal vetor de valores.
	std::vector<T> retrieve(const char * path, GTrie<T>** rpointer);

	// Remove os valores que o no apontado pela chave path
	// representa da trie ao qual
	// ele esta relacionado, e os nos que se tornaram inuteis
	void remove(std::string path);

	// Remove os valores que o no representa da trie ao qual
	// ele esta relacionado, e os nos que se tornaram inuteis
	void remove();
};

#include <GTrie.inl>

#endif
